package com.hyc.algorithm.sort;

import java.util.ArrayList;

/**
 * @projectName: DataStructure
 * @package: com.hyc.algorithm.sort
 * @className: QuickSort
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/4/3 23:30
 * @version: 1.0
 */
public class QuickSort {
    public static void main(String[] args) {
        //ArrayList<Integer> arr = new ArrayList<>();
        //arr.add(3);
        //arr.add(1);
        //arr.add(9);
        //arr.add(2);
        //arr.add(6);
        //arr.add(8);
        //arr.add(7);
        //arr.add(5);
        //System.out.println(quickSort(arr));
        int[] arr = {3, 1, 9, 2, 6, 8, 7, 5};
        int[] test = new int[8000000];
        //测试数据
        for (int i = 0; i < 8000000; i++) {
            test[i] = (int) (Math.random() * 800000);
        }
        long time = System.currentTimeMillis();
        quickSort(arr);
        long end = System.currentTimeMillis();
        long t = ((end - time) / 1000);
        System.out.println("一共用时 " + t + "秒");
    }


    //简易版本
    public static ArrayList<Integer> quickSort(ArrayList<Integer> arr) {
        if (arr == null || arr.size() <= 1) {
            return arr;
        }
        int leader = arr.get(0);
        //存放左右的结果
        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right = new ArrayList<>();
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i) <= leader) {
                left.add(arr.get(i));
            } else {
                right.add(arr.get(i));
            }
        }
        //递归
        ArrayList<Integer> leftResult = quickSort(left);
        ArrayList<Integer> rightResult = quickSort(right);
        //    合并
        ArrayList<Integer> result = new ArrayList<>();
        result.addAll(leftResult);
        result.add(leader);
        result.addAll(rightResult);
        return result;
    }


    //标准版快速排序
    public static void quickSort(int[] arr) {
        optimizeQuickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        //已经交换过一次 中间值的为止不会变化了
        int partPoint = partition(arr, low, high);
        //递归左边
        quickSort(arr, low, partPoint - 1);
        //递归右边
        quickSort(arr, partPoint + 1, high);
    }

    //进行一次左右换位
    public static int partition(int[] arr, int low, int high) {
        int leader = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= leader) {
                //从右边寻找第一个小于leader的数字
                high--;
            }
            //    交换值
            arr[low] = arr[high];

            while (low < high && arr[low] <= leader) {
                //从左边找到第一个大于leader的数字
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = leader;
        return low;
    }

    //速度优化之后的快速排序
    public static void optimizeQuickSort(int[] arr, int low, int high) {
        int l = low;
        int r = high;
        int pivot = arr[l + r / 2];
        int temp = 0;
        while (l < r) {
            while (arr[l] < pivot) {
                l += 1;
            }
            while (arr[r] > pivot) {
                r -= 1;
            }
            if (l >= r) {
                break;
            }

            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            if (arr[l] == pivot) {
                r -= 1;
            }
            if (arr[r] == pivot) {
                l += 1;
            }
        }
        //防止栈溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }

        //防止栈溢出，当low指针0 r = 0 的时候就不许要排序递归左边了，
        if (low < r) {
            quickSort(arr, low, r);
        }
        //当 高位大于 左边指针的时候 就需要向右边递归了
        if (high > l) {
            quickSort(arr, l, high);
        }
    }

}
